# Copyright 2024 by UltrafunkAmsterdam (https://github.com/UltrafunkAmsterdam)
# All rights reserved.
# This file is part of the nodriver package.
# and is released under the "GNU AFFERO GENERAL PUBLIC LICENSE".
# Please see the LICENSE.txt file that should have been included as part of this package.


from __future__ import annotations

import asyncio
import logging
import shutil
import types
from ssl import SSLContext
from typing import (TYPE_CHECKING, Any, Callable, Generator, List, Optional,
                    Set, Tuple, TypeVar, Union)

from .element import Element

if TYPE_CHECKING:
    from .browser import Browser, PathLike

from .. import cdp
from .config import Config

__registered__instances__: Set[Browser] = set()

logger = logging.getLogger(__name__)
T = TypeVar("T")


async def start(
    config: Optional[Config] = None,
    *,
    user_data_dir: Optional[PathLike] = None,
    headless: Optional[bool] = False,
    browser_executable_path: Optional[PathLike] = None,
    browser_args: Optional[List[str]] = None,
    sandbox: Optional[bool] = True,
    lang: Optional[str] = None,
    host: Optional[str] = None,
    port: Optional[int] = None,
    expert: Optional[bool] = None,
    **kwargs: Optional[dict],
) -> Browser:
    """
    helper function to launch a browser. it accepts several keyword parameters.
    conveniently, you can just call it bare (no parameters) to quickly launch an instance
    with best practice defaults.
    note: this should be called ```await start()```


    :param user_data_dir:
    :type user_data_dir: PathLike

    :param headless:
    :type headless: bool

    :param browser_executable_path:
    :type browser_executable_path: PathLike

    :param browser_args: ["--some-chromeparam=somevalue", "some-other-param=someval"]
    :type browser_args: List[str]

    :param sandbox: default True, but when set to False it adds --no-sandbox to the params, also
    when using linux under a root user, it adds False automatically (else chrome won't start
    :type sandbox: bool

    :param lang: language string
    :type lang: str

    :param port: if you connect to an existing debuggable session, you can specify the port here
                 if both host and port are provided, nodriver will not start a local chrome browser!
    :type port: int

    :param host: if you connect to an existing debuggable session, you can specify the host here
                 if both host and port are provided, nodriver will not start a local chrome browser!
    :type host: str

    :param expert:  when set to True, enabled "expert" mode.
                    This conveys, the inclusion of parameters: --disable-web-security ----disable-site-isolation-trials,
                    as well as some scripts and patching useful for debugging (for example, ensuring shadow-root is always in "open" mode)
    :type expert: bool

    :return:
    """
    if not config:
        config = Config(
            user_data_dir,
            headless,
            browser_executable_path,
            browser_args,
            sandbox,
            lang,
            host=host,
            port=port,
            expert=expert,
            **kwargs,
        )
    from .browser import Browser

    return await Browser.create(config)


async def create_from_undetected_chromedriver(
    driver: "undetected_chromedriver.Chrome",
) -> Browser:
    """
    create a nodriver.Browser instance from a running undetected_chromedriver.Chrome instance.
    """
    from .config import Config

    conf = Config()

    host, port = driver.options.debugger_address.split(":")
    conf.host, conf.port = host, int(port)

    # create nodriver Browser instance
    browser = await start(conf)

    browser._process_pid = driver.browser_pid
    # stop chromedriver binary
    driver.service.stop()
    driver.browser_pid = -1
    driver.user_data_dir = None
    return browser


def get_registered_instances():
    return __registered__instances__


def free_port() -> int:
    """
    Determines a free port using sockets.
    """
    import socket

    free_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    free_socket.bind(("127.0.0.1", 0))
    free_socket.listen(5)
    port: int = free_socket.getsockname()[1]
    free_socket.close()
    return port


def deconstruct_browser(browser: Browser = None):
    """
    deconstructs all sessions and cleans up any leftover temp files (profile)
    it requires no params.
    if however, a browser instance is passed as argument, then run an async cleanup
    routine for that instance only. (this is used for :py:class:`browser.BrowserContext`  context manager)

    :param browser: optional - the browser instance to cleanup the single instance
    :ptype browser: browser.Browser
    """
    import time

    if browser is not None:

        async def deconstruct(b: Browser):
            if not b.stopped:
                b.stop()
            config = b.config
            if not config.uses_custom_data_dir:
                for _ in range(3):
                    try:
                        shutil.rmtree(config.user_data_dir, ignore_errors=False)
                        print(
                            "successfully removed temp profile %s"
                            % config.user_data_dir
                        )
                        break
                    except (Exception,):
                        await asyncio.sleep(0.250)

        return asyncio.get_running_loop().create_task(deconstruct(browser))

    for _ in __registered__instances__:
        if not _.stopped:
            _.stop()
        for attempt in range(5):
            try:
                if _.config and not _.config.uses_custom_data_dir:
                    shutil.rmtree(_.config.user_data_dir, ignore_errors=False)
                    print(
                        "successfully removed temp profile %s" % _.config.user_data_dir
                    )
            except FileNotFoundError as e:
                break
            except (PermissionError, OSError) as e:
                if attempt == 4:
                    logger.debug(
                        "problem removing data dir %s\nConsider checking whether it's there and remove it by hand\nerror: %s",
                        _.config.user_data_dir,
                        e,
                    )
                    break
                time.sleep(0.15)
                continue
    __registered__instances__.clear()


def filter_recurse_all(
    doc: T, predicate: Callable[[cdp.dom.Node, Element], bool]
) -> List[T]:
    """
    test each child using predicate(child), and return all children for which predicate(child) == True

    :param doc: the cdp.dom.Node object or :py:class:`nodriver.Element`
    :param predicate: a function which takes a node as first parameter and returns a boolean, where True means include
    :return:
    :rtype:
    """
    if not hasattr(doc, "children"):
        raise TypeError("object should have a .children attribute")
    out = []
    if doc and doc.children:
        for child in doc.children:
            if predicate(child):
                # if predicate is True
                out.append(child)
            if child.shadow_roots is not None:
                out.extend(filter_recurse_all(child.shadow_roots[0], predicate))
            out.extend(filter_recurse_all(child, predicate))

    return out


def filter_recurse(doc: T, predicate: Callable[[cdp.dom.Node, Element], bool]) -> T:
    """
    test each child using predicate(child), and return the first child of which predicate(child) == True

    :param doc: the cdp.dom.Node object or :py:class:`nodriver.Element`
    :param predicate: a function which takes a node as first parameter and returns a boolean, where True means include

    """
    if not hasattr(doc, "children"):
        raise TypeError("object should have a .children attribute")

    if doc and doc.children:
        for child in doc.children:
            if predicate(child):
                # if predicate is True
                return child
            if child.shadow_roots:
                shadow_root_result = filter_recurse(child.shadow_roots[0], predicate)
                if shadow_root_result:
                    return shadow_root_result
            result = filter_recurse(child, predicate)
            if result:
                return result


def flatten_frame_tree(
    tree: Union[cdp.page.FrameResourceTree, cdp.page.FrameTree],
) -> Generator[cdp.page.Frame, None, None]:
    yield tree.frame
    if tree.child_frames:
        for child in tree.child_frames:
            yield from flatten_frame_tree(child)


def flatten_frame_tree_resources(
    tree: cdp.page.FrameResourceTree,
) -> Generator[Tuple[cdp.page.Frame, cdp.page.FrameResource], None, None]:
    for res in tree.resources:
        yield tree.frame, res
    if tree.child_frames:
        for child in tree.child_frames:
            yield from flatten_frame_tree(child)


def get_all_param_names(cls):
    comp = cls.mro()
    ret = []
    for c in comp:
        if not hasattr(c, "__annotations__"):
            continue
        for ann in c.__annotations__:
            if ann not in ret:
                ret.append(ann)
    return ret


def circle(
    x, y=None, radius=10, num=10, dir=0
) -> Generator[Tuple[float, float], None, None]:
    """
    a generator will calculate coordinates around a circle.

    :param x: start x position
    :type x: int
    :param y: start y position
    :type y: int
    :param radius: size of the circle
    :type radius: int
    :param num: the amount of points calculated (higher => slower, more cpu, but more detailed)
    :type num: int
    :return:
    :rtype:
    """
    import math

    r = radius
    w = num
    if not y:
        y = x
    a = int(x - r * 2)
    b = int(y - r * 2)
    m = (2 * math.pi) / w
    if dir == 0:
        # regular direction
        ran = 0, w + 1, 1
    else:
        # opposite ?
        ran = w + 1, 0, -1

    for i in range(*ran):
        x = a + r * math.sin(m * i)
        y = b + r * math.cos(m * i)

        yield x, y


def remove_from_tree(tree: cdp.dom.Node, node: cdp.dom.Node) -> cdp.dom.Node:
    if not hasattr(tree, "children"):
        raise TypeError("object should have a .children attribute")

    if tree and tree.children:
        for child in tree.children:
            if child.backend_node_id == node.backend_node_id:
                tree.children.remove(child)
            remove_from_tree(child, node)
    return tree


async def html_from_tree(tree: Union[cdp.dom.Node, Element], target: "nodriver.Tab"):
    if not hasattr(tree, "children"):
        raise TypeError("object should have a .children attribute")
    out = ""
    if tree and tree.children:
        for child in tree.children:
            if isinstance(child, Element):
                out += await child.get_html()
            else:
                out += await target.send(
                    cdp.dom.get_outer_html(backend_node_id=child.backend_node_id)
                )
            out += await html_from_tree(child, target)
    return out


def compare_target_info(
    info1: cdp.target.TargetInfo, info2: cdp.target.TargetInfo
) -> List[Tuple[str, Any, Any]]:
    """
    when logging mode is set to debug, browser object will log when target info
    is changed. To provide more meaningful log messages, this function is called to
    check what has actually changed between the 2 (by simple dict comparison).
    it returns a list of tuples [ ... ( key_which_has_changed, old_value, new_value) ]

    :param info1:
    :type info1:
    :param info2:
    :type info2:
    :return:
    :rtype:
    """
    d1 = info1.__dict__
    d2 = info2.__dict__
    return [(k, v, d2[k]) for (k, v) in d1.items() if d2[k] != v]


def loop():
    loop = asyncio.new_event_loop()
    asyncio.set_event_loop(loop)
    return loop


def cdp_get_module(domain: Union[str, types.ModuleType]):
    """
    get cdp module by given string

    :param domain:
    :type domain:
    :return:
    :rtype:
    """
    import importlib

    if isinstance(domain, types.ModuleType):
        # you get what you ask for
        domain_mod = domain
    else:
        try:
            if domain in ("input",):
                domain = "input_"

            #  fallback if someone passes a str
            domain_mod = getattr(cdp, domain)
            if not domain_mod:
                raise AttributeError
        except AttributeError:
            try:
                domain_mod = importlib.import_module(domain)
            except ModuleNotFoundError:
                raise ModuleNotFoundError(
                    "could not find cdp module from input '%s'" % domain
                )
    return domain_mod


def get_cf_template() -> bytearray:
    """
    this returns a template image (of a checkbox)
    like this: https://ultrafunkamsterdam.github.io/nodriver/_images/template_example.png
    didn't bother the hassle to include image files in my package.
    :return:
    :rtype:
    """
    return bytearray(
        [
            137,
            80,
            78,
            71,
            13,
            10,
            26,
            10,
            0,
            0,
            0,
            13,
            73,
            72,
            68,
            82,
            0,
            0,
            0,
            111,
            0,
            0,
            0,
            73,
            8,
            6,
            0,
            0,
            0,
            51,
            48,
            120,
            75,
            0,
            0,
            0,
            1,
            115,
            82,
            71,
            66,
            0,
            174,
            206,
            28,
            233,
            0,
            0,
            0,
            4,
            103,
            65,
            77,
            65,
            0,
            0,
            177,
            143,
            11,
            252,
            97,
            5,
            0,
            0,
            0,
            9,
            112,
            72,
            89,
            115,
            0,
            0,
            14,
            195,
            0,
            0,
            14,
            195,
            1,
            199,
            111,
            168,
            100,
            0,
            0,
            15,
            213,
            73,
            68,
            65,
            84,
            120,
            94,
            237,
            92,
            105,
            172,
            85,
            213,
            25,
            93,
            119,
            158,
            223,
            192,
            123,
            128,
            96,
            9,
            210,
            2,
            162,
            17,
            67,
            109,
            165,
            145,
            161,
            32,
            134,
            65,
            69,
            193,
            52,
            237,
            175,
            214,
            214,
            214,
            136,
            52,
            105,
            171,
            5,
            106,
            210,
            212,
            90,
            192,
            40,
            21,
            19,
            127,
            52,
            246,
            159,
            65,
            165,
            166,
            150,
            198,
            161,
            168,
            37,
            14,
            209,
            130,
            3,
            56,
            80,
            177,
            104,
            20,
            172,
            32,
            195,
            147,
            65,
            129,
            55,
            220,
            121,
            236,
            90,
            251,
            220,
            253,
            184,
            128,
            76,
            245,
            62,
            251,
            110,
            223,
            89,
            186,
            57,
            231,
            236,
            121,
            127,
            107,
            127,
            223,
            254,
            246,
            57,
            251,
            62,
            79,
            133,
            192,
            151,
            136,
            227,
            27,
            243,
            84,
            175,
            39,
            197,
            73,
            11,
            20,
            25,
            188,
            76,
            103,
            16,
            60,
            5,
            231,
            90,
            9,
            56,
            215,
            19,
            158,
            245,
            143,
            202,
            168,
            66,
            31,
            42,
            42,
            103,
            226,
            148,
            175,
            204,
            16,
            50,
            255,
            86,
            107,
            35,
            114,
            12,
            122,
            98,
            121,
            22,
            241,
            120,
            148,
            90,
            230,
            173,
            223,
            41,
            86,
            225,
            51,
            111,
            242,
            204,
            163,
            92,
            254,
            146,
            210,
            249,
            236,
            115,
            106,
            8,
            150,
            249,
            204,
            114,
            21,
            62,
            43,
            197,
            103,
            98,
            85,
            190,
            218,
            108,
            73,
            55,
            94,
            20,
            153,
            93,
            233,
            65,
            197,
            153,
            177,
            150,
            249,
            95,
            17,
            69,
            143,
            218,
            41,
            33,
            144,
            103,
            164,
            215,
            135,
            130,
            46,
            1,
            95,
            111,
            255,
            84,
            166,
            79,
            200,
            43,
            179,
            227,
            30,
            143,
            135,
            2,
            170,
            152,
            123,
            191,
            223,
            143,
            66,
            161,
            128,
            64,
            160,
            42,
            200,
            186,
            64,
            221,
            183,
            67,
            17,
            244,
            44,
            212,
            14,
            79,
            56,
            85,
            30,
            225,
            104,
            92,
            175,
            96,
            13,
            78,
            150,
            183,
            250,
            92,
            205,
            108,
            133,
            231,
            169,
            222,
            84,
            170,
            21,
            216,
            103,
            155,
            231,
            104,
            189,
            85,
            28,
            159,
            95,
            255,
            244,
            150,
            17,
            201,
            106,
            135,
            114,
            236,
            157,
            156,
            199,
            214,
            99,
            238,
            235,
            77,
            158,
            37,
            204,
            231,
            115,
            230,
            154,
            139,
            190,
            195,
            151,
            98,
            54,
            51,
            153,
            140,
            33,
            213,
            235,
            245,
            34,
            20,
            10,
            85,
            99,
            93,
            124,
            81,
            244,
            41,
            121,
            210,
            192,
            82,
            169,
            132,
            131,
            7,
            15,
            34,
            24,
            12,
            26,
            2,
            115,
            57,
            173,
            37,
            46,
            234,
            129,
            186,
            147,
            39,
            194,
            4,
            173,
            121,
            34,
            78,
            218,
            214,
            209,
            209,
            129,
            65,
            131,
            6,
            153,
            120,
            173,
            127,
            46,
            234,
            131,
            62,
            213,
            60,
            145,
            167,
            181,
            111,
            215,
            174,
            93,
            24,
            49,
            98,
            132,
            209,
            60,
            23,
            245,
            195,
            151,
            66,
            222,
            135,
            31,
            126,
            136,
            81,
            163,
            70,
            245,
            106,
            165,
            139,
            250,
            160,
            238,
            228,
            169,
            58,
            153,
            204,
            218,
            251,
            237,
            219,
            183,
            99,
            244,
            232,
            209,
            134,
            76,
            155,
            230,
            226,
            139,
            163,
            207,
            200,
            147,
            150,
            105,
            189,
            19,
            246,
            236,
            217,
            131,
            161,
            67,
            135,
            154,
            231,
            58,
            55,
            55,
            160,
            81,
            187,
            3,
            117,
            209,
            96,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            163,
            223,
            125,
            207,
            83,
            186,
            190,
            190,
            247,
            244,
            244,
            32,
            30,
            143,
            155,
            51,
            47,
            170,
            43,
            155,
            205,
            226,
            177,
            199,
            30,
            195,
            214,
            173,
            91,
            81,
            44,
            22,
            77,
            80,
            252,
            241,
            31,
            119,
            109,
            155,
            39,
            131,
            202,
            68,
            34,
            17,
            83,
            191,
            14,
            69,
            77,
            158,
            60,
            25,
            243,
            230,
            205,
            235,
            45,
            167,
            179,
            165,
            58,
            237,
            22,
            14,
            135,
            209,
            217,
            217,
            137,
            214,
            214,
            86,
            83,
            38,
            159,
            207,
            155,
            182,
            244,
            65,
            57,
            26,
            141,
            154,
            60,
            246,
            120,
            163,
            202,
            40,
            77,
            117,
            170,
            220,
            169,
            160,
            50,
            182,
            30,
            29,
            198,
            82,
            93,
            221,
            221,
            221,
            72,
            36,
            18,
            166,
            15,
            26,
            151,
            160,
            113,
            171,
            77,
            93,
            21,
            167,
            186,
            219,
            218,
            218,
            204,
            249,
            87,
            139,
            126,
            71,
            158,
            242,
            168,
            131,
            246,
            160,
            146,
            6,
            169,
            65,
            172,
            95,
            191,
            222,
            4,
            9,
            77,
            121,
            20,
            212,
            142,
            173,
            79,
            247,
            138,
            19,
            201,
            167,
            130,
            210,
            37,
            48,
            9,
            89,
            249,
            37,
            184,
            89,
            179,
            102,
            97,
            246,
            236,
            217,
            38,
            62,
            157,
            78,
            155,
            124,
            186,
            183,
            7,
            133,
            107,
            15,
            12,
            235,
            94,
            125,
            18,
            241,
            42,
            47,
            168,
            142,
            88,
            44,
            102,
            136,
            169,
            21,
            238,
            231,
            65,
            99,
            209,
            241,
            71,
            229,
            85,
            61,
            130,
            37,
            74,
            109,
            107,
            194,
            234,
            170,
            186,
            21,
            175,
            124,
            106,
            91,
            227,
            84,
            254,
            90,
            249,
            245,
            59,
            242,
            212,
            217,
            84,
            42,
            101,
            102,
            162,
            58,
            43,
            97,
            171,
            220,
            138,
            21,
            43,
            176,
            119,
            239,
            94,
            172,
            92,
            185,
            210,
            12,
            94,
            65,
            241,
            202,
            99,
            219,
            82,
            80,
            249,
            211,
            193,
            230,
            223,
            183,
            111,
            31,
            150,
            47,
            95,
            142,
            246,
            246,
            118,
            44,
            89,
            178,
            228,
            24,
            65,
            89,
            225,
            218,
            62,
            52,
            53,
            53,
            25,
            1,
            75,
            107,
            53,
            129,
            116,
            21,
            105,
            186,
            74,
            131,
            84,
            159,
            202,
            137,
            212,
            83,
            65,
            132,
            72,
            139,
            68,
            182,
            234,
            179,
            117,
            74,
            187,
            236,
            132,
            210,
            189,
            100,
            168,
            62,
            232,
            94,
            245,
            170,
            156,
            142,
            80,
            218,
            83,
            120,
            194,
            169,
            109,
            204,
            255,
            8,
            26,
            128,
            160,
            78,
            235,
            94,
            131,
            234,
            234,
            234,
            50,
            179,
            82,
            66,
            212,
            192,
            53,
            24,
            165,
            73,
            216,
            34,
            82,
            87,
            13,
            86,
            196,
            156,
            42,
            212,
            66,
            19,
            74,
            144,
            121,
            212,
            100,
            177,
            103,
            75,
            149,
            79,
            132,
            168,
            13,
            213,
            173,
            118,
            85,
            183,
            21,
            166,
            37,
            213,
            106,
            134,
            210,
            149,
            79,
            218,
            122,
            58,
            136,
            20,
            65,
            229,
            212,
            231,
            230,
            230,
            102,
            67,
            160,
            202,
            170,
            110,
            171,
            249,
            154,
            48,
            186,
            87,
            63,
            212,
            150,
            202,
            217,
            254,
            90,
            244,
            59,
            242,
            36,
            60,
            59,
            187,
            37,
            68,
            117,
            90,
            131,
            147,
            57,
            18,
            89,
            10,
            181,
            100,
            88,
            97,
            107,
            128,
            26,
            188,
            205,
            115,
            178,
            160,
            252,
            130,
            213,
            22,
            9,
            77,
            101,
            21,
            175,
            54,
            116,
            149,
            96,
            237,
            228,
            176,
            109,
            40,
            77,
            253,
            80,
            127,
            148,
            166,
            182,
            172,
            192,
            37,
            104,
            105,
            147,
            173,
            251,
            84,
            80,
            29,
            154,
            40,
            202,
            175,
            114,
            42,
            111,
            181,
            53,
            153,
            76,
            154,
            171,
            234,
            87,
            221,
            138,
            215,
            68,
            213,
            85,
            242,
            56,
            222,
            36,
            247,
            59,
            242,
            212,
            65,
            9,
            72,
            130,
            144,
            240,
            172,
            25,
            211,
            189,
            132,
            172,
            171,
            77,
            23,
            116,
            175,
            56,
            43,
            240,
            51,
            129,
            205,
            47,
            168,
            140,
            234,
            18,
            73,
            210,
            30,
            61,
            171,
            77,
            93,
            53,
            243,
            237,
            250,
            35,
            178,
            165,
            97,
            234,
            131,
            44,
            129,
            202,
            136,
            8,
            165,
            233,
            185,
            165,
            165,
            197,
            16,
            114,
            58,
            136,
            44,
            219,
            103,
            213,
            39,
            168,
            46,
            17,
            39,
            147,
            104,
            219,
            213,
            210,
            161,
            250,
            44,
            97,
            106,
            95,
            229,
            106,
            209,
            47,
            205,
            166,
            132,
            34,
            129,
            88,
            178,
            172,
            73,
            84,
            231,
            37,
            100,
            65,
            207,
            74,
            59,
            91,
            88,
            1,
            168,
            172,
            234,
            146,
            160,
            36,
            80,
            171,
            185,
            54,
            216,
            182,
            164,
            37,
            18,
            232,
            225,
            195,
            135,
            205,
            179,
            250,
            166,
            171,
            202,
            171,
            140,
            210,
            118,
            239,
            222,
            109,
            234,
            148,
            73,
            63,
            29,
            84,
            70,
            65,
            26,
            165,
            53,
            92,
            196,
            105,
            210,
            216,
            122,
            165,
            101,
            34,
            77,
            196,
            202,
            211,
            149,
            198,
            9,
            146,
            135,
            218,
            170,
            69,
            191,
            35,
            79,
            3,
            145,
            240,
            36,
            28,
            205,
            54,
            5,
            193,
            14,
            78,
            131,
            173,
            157,
            129,
            122,
            150,
            48,
            116,
            61,
            51,
            148,
            57,
            155,
            29,
            147,
            169,
            80,
            97,
            85,
            161,
            72,
            24,
            1,
            10,
            173,
            84,
            113,
            72,
            49,
            109,
            240,
            63,
            253,
            212,
            142,
            58,
            142,
            92,
            170,
            27,
            107,
            30,
            121,
            24,
            43,
            239,
            89,
            129,
            24,
            133,
            218,
            149,
            162,
            19,
            197,
            252,
            65,
            57,
            45,
            93,
            105,
            44,
            93,
            186,
            28,
            79,
            61,
            179,
            22,
            135,
            59,
            15,
            193,
            87,
            166,
            86,
            51,
            168,
            157,
            138,
            71,
            63,
            209,
            146,
            87,
            232,
            136,
            89,
            63,
            219,
            138,
            115,
            50,
            164,
            82,
            25,
            116,
            31,
            62,
            132,
            27,
            126,
            244,
            125,
            252,
            245,
            137,
            39,
            145,
            47,
            151,
            48,
            168,
            57,
            138,
            157,
            59,
            182,
            99,
            204,
            133,
            23,
            227,
            242,
            89,
            115,
            177,
            225,
            31,
            47,
            171,
            0,
            11,
            115,
            210,
            178,
            79,
            168,
            20,
            144,
            73,
            119,
            155,
            122,
            28,
            218,
            216,
            127,
            231,
            161,
            255,
            64,
            196,
            217,
            153,
            40,
            187,
            47,
            13,
            19,
            57,
            138,
            19,
            105,
            214,
            220,
            89,
            216,
            184,
            90,
            66,
            79,
            14,
            105,
            109,
            25,
            62,
            191,
            242,
            114,
            157,
            36,
            89,
            21,
            105,
            24,
            197,
            144,
            45,
            80,
            219,
            124,
            52,
            209,
            188,
            87,
            123,
            74,
            247,
            202,
            100,
            21,
            179,
            8,
            121,
            43,
            248,
            206,
            149,
            51,
            241,
            192,
            31,
            239,
            199,
            174,
            189,
            135,
            224,
            97,
            191,
            52,
            165,
            58,
            179,
            92,
            239,
            50,
            21,
            108,
            126,
            227,
            29,
            76,
            184,
            116,
            2,
            34,
            9,
            110,
            31,
            216,
            151,
            98,
            58,
            79,
            211,
            80,
            36,
            41,
            25,
            248,
            61,
            212,
            150,
            18,
            219,
            35,
            9,
            185,
            34,
            61,
            99,
            18,
            226,
            173,
            4,
            225,
            39,
            25,
            207,
            191,
            176,
            14,
            115,
            191,
            247,
            93,
            164,
            203,
            108,
            199,
            147,
            198,
            138,
            101,
            191,
            193,
            210,
            223,
            223,
            143,
            151,
            223,
            120,
            19,
            151,
            125,
            125,
            34,
            103,
            108,
            129,
            19,
            43,
            134,
            100,
            182,
            128,
            112,
            68,
            147,
            34,
            205,
            9,
            92,
            132,
            63,
            192,
            45,
            73,
            81,
            189,
            30,
            128,
            224,
            254,
            168,
            122,
            39,
            50,
            29,
            237,
            19,
            105,
            230,
            158,
            105,
            70,
            139,
            249,
            191,
            79,
            19,
            66,
            191,
            128,
            37,
            121,
            173,
            77,
            49,
            92,
            120,
            254,
            88,
            188,
            185,
            121,
            11,
            242,
            228,
            150,
            244,
            192,
            227,
            247,
            225,
            241,
            39,
            158,
            198,
            196,
            111,
            77,
            198,
            176,
            33,
            109,
            40,
            147,
            232,
            124,
            119,
            22,
            193,
            120,
            4,
            94,
            15,
            77,
            99,
            48,
            192,
            73,
            72,
            97,
            251,
            181,
            78,
            123,
            233,
            136,
            5,
            185,
            189,
            40,
            81,
            251,
            130,
            136,
            182,
            36,
            240,
            217,
            254,
            79,
            144,
            229,
            100,
            245,
            249,
            195,
            232,
            62,
            208,
            129,
            131,
            251,
            58,
            48,
            98,
            212,
            24,
            244,
            112,
            171,
            26,
            136,
            134,
            76,
            219,
            250,
            193,
            45,
            167,
            27,
            91,
            211,
            118,
            129,
            125,
            44,
            123,
            208,
            217,
            157,
            33,
            169,
            129,
            129,
            73,
            222,
            241,
            48,
            166,
            173,
            122,
            47,
            24,
            242,
            140,
            178,
            80,
            60,
            230,
            222,
            131,
            22,
            58,
            19,
            83,
            166,
            78,
            195,
            163,
            127,
            249,
            179,
            225,
            92,
            191,
            50,
            12,
            249,
            60,
            216,
            240,
            218,
            70,
            92,
            117,
            245,
            92,
            154,
            180,
            78,
            138,
            184,
            136,
            153,
            87,
            207,
            195,
            152,
            209,
            227,
            25,
            190,
            134,
            123,
            239,
            189,
            27,
            1,
            10,
            153,
            10,
            138,
            7,
            87,
            175,
            198,
            130,
            133,
            11,
            177,
            228,
            87,
            183,
            98,
            228,
            200,
            175,
            226,
            173,
            13,
            27,
            176,
            244,
            183,
            75,
            241,
            204,
            218,
            103,
            176,
            103,
            111,
            7,
            174,
            153,
            59,
            31,
            91,
            183,
            190,
            135,
            89,
            179,
            102,
            224,
            250,
            235,
            127,
            130,
            155,
            127,
            124,
            3,
            158,
            92,
            243,
            40,
            215,
            123,
            173,
            119,
            94,
            28,
            248,
            228,
            0,
            126,
            121,
            235,
            18,
            172,
            90,
            181,
            154,
            207,
            17,
            106,
            125,
            114,
            0,
            146,
            39,
            46,
            164,
            106,
            132,
            72,
            163,
            82,
            29,
            131,
            94,
            243,
            43,
            210,
            12,
            121,
            100,
            74,
            121,
            18,
            77,
            152,
            52,
            101,
            178,
            249,
            221,
            69,
            62,
            157,
            65,
            62,
            151,
            196,
            166,
            87,
            214,
            99,
            203,
            191,
            182,
            226,
            210,
            203,
            38,
            209,
            186,
            166,
            112,
            237,
            85,
            87,
            98,
            241,
            109,
            191,
            198,
            187,
            239,
            111,
            197,
            230,
            215,
            55,
            225,
            239,
            79,
            175,
            197,
            246,
            29,
            29,
            52,
            123,
            244,
            106,
            3,
            65,
            172,
            127,
            233,
            69,
            44,
            92,
            112,
            35,
            118,
            237,
            254,
            55,
            190,
            57,
            241,
            82,
            99,
            158,
            163,
            225,
            4,
            206,
            25,
            60,
            28,
            47,
            189,
            248,
            42,
            198,
            158,
            63,
            14,
            47,
            60,
            255,
            28,
            158,
            250,
            219,
            3,
            152,
            58,
            125,
            18,
            214,
            191,
            242,
            18,
            104,
            105,
            65,
            229,
            69,
            142,
            150,
            245,
            229,
            87,
            223,
            194,
            156,
            217,
            87,
            211,
            169,
            113,
            186,
            52,
            112,
            53,
            143,
            163,
            23,
            77,
            10,
            181,
            4,
            138,
            60,
            57,
            45,
            101,
            179,
            30,
            82,
            201,
            148,
            38,
            2,
            121,
            63,
            246,
            130,
            113,
            124,
            40,
            99,
            203,
            219,
            155,
            185,
            174,
            117,
            227,
            205,
            141,
            175,
            96,
            193,
            205,
            63,
            229,
            122,
            153,
            199,
            190,
            221,
            31,
            35,
            66,
            53,
            153,
            60,
            109,
            26,
            188,
            97,
            160,
            181,
            173,
            29,
            55,
            223,
            180,
            0,
            15,
            62,
            180,
            154,
            107,
            33,
            48,
            100,
            200,
            57,
            184,
            228,
            27,
            19,
            48,
            118,
            204,
            72,
            154,
            203,
            61,
            82,
            39,
            154,
            208,
            36,
            82,
            12,
            177,
            144,
            7,
            93,
            93,
            73,
            106,
            89,
            4,
            93,
            71,
            62,
            53,
            164,
            204,
            156,
            53,
            29,
            239,
            189,
            255,
            46,
            54,
            111,
            121,
            155,
            222,
            103,
            22,
            27,
            55,
            110,
            193,
            148,
            41,
            87,
            224,
            188,
            81,
            195,
            233,
            196,
            1,
            241,
            112,
            108,
            32,
            146,
            87,
            29,
            178,
            200,
            179,
            65,
            177,
            53,
            4,
            114,
            193,
            34,
            105,
            92,
            251,
            184,
            78,
            145,
            54,
            102,
            80,
            25,
            15,
            6,
            181,
            183,
            225,
            182,
            37,
            139,
            240,
            240,
            67,
            15,
            32,
            26,
            10,
            226,
            233,
            167,
            214,
            98,
            220,
            5,
            99,
            48,
            226,
            220,
            102,
            28,
            220,
            127,
            0,
            219,
            62,
            248,
            128,
            218,
            57,
            5,
            35,
            70,
            78,
            192,
            249,
            163,
            199,
            98,
            241,
            226,
            197,
            232,
            73,
            165,
            209,
            195,
            189,
            247,
            158,
            142,
            14,
            227,
            250,
            39,
            18,
            97,
            180,
            15,
            107,
            231,
            134,
            54,
            139,
            8,
            9,
            8,
            144,
            233,
            30,
            58,
            145,
            173,
            195,
            207,
            67,
            231,
            145,
            110,
            198,
            57,
            239,
            80,
            135,
            140,
            24,
            134,
            25,
            51,
            167,
            227,
            217,
            103,
            159,
            197,
            160,
            214,
            176,
            89,
            91,
            127,
            240,
            195,
            27,
            233,
            208,
            105,
            111,
            10,
            244,
            116,
            117,
            14,
            76,
            179,
            249,
            249,
            160,
            247,
            38,
            109,
            35,
            105,
            210,
            188,
            94,
            248,
            233,
            129,
            250,
            252,
            40,
            209,
            243,
            244,
            82,
            106,
            211,
            105,
            58,
            119,
            239,
            216,
            129,
            117,
            235,
            214,
            97,
            48,
            181,
            235,
            219,
            147,
            46,
            54,
            214,
            53,
            95,
            40,
            99,
            206,
            149,
            115,
            177,
            241,
            181,
            13,
            216,
            187,
            123,
            11,
            182,
            125,
            244,
            17,
            118,
            238,
            222,
            135,
            123,
            86,
            46,
            227,
            6,
            222,
            121,
            249,
            160,
            109,
            79,
            79,
            234,
            8,
            178,
            169,
            46,
            70,
            112,
            207,
            152,
            163,
            23,
            205,
            186,
            233,
            11,
            161,
            76,
            15,
            53,
            18,
            137,
            34,
            17,
            11,
            161,
            155,
            251,
            188,
            100,
            247,
            17,
            76,
            159,
            121,
            57,
            94,
            167,
            249,
            253,
            231,
            150,
            237,
            40,
            208,
            124,
            94,
            112,
            209,
            197,
            200,
            208,
            142,
            42,
            125,
            112,
            83,
            235,
            0,
            35,
            207,
            254,
            89,
            140,
            94,
            232,
            185,
            186,
            23,
            115,
            34,
            28,
            103,
            197,
            94,
            233,
            222,
            123,
            189,
            220,
            134,
            112,
            11,
            33,
            215,
            92,
            113,
            225,
            144,
            31,
            23,
            141,
            27,
            131,
            219,
            111,
            191,
            3,
            227,
            199,
            143,
            71,
            144,
            142,
            96,
            62,
            93,
            196,
            180,
            25,
            115,
            240,
            206,
            187,
            31,
            224,
            53,
            174,
            131,
            93,
            157,
            122,
            43,
            194,
            253,
            106,
            69,
            175,
            209,
            128,
            116,
            26,
            104,
            31,
            50,
            148,
            10,
            236,
            231,
            122,
            21,
            64,
            56,
            22,
            101,
            90,
            217,
            188,
            124,
            136,
            132,
            194,
            200,
            113,
            31,
            158,
            229,
            162,
            38,
            7,
            169,
            144,
            77,
            35,
            17,
            15,
            32,
            222,
            148,
            192,
            132,
            75,
            46,
            97,
            185,
            54,
            220,
            121,
            231,
            114,
            58,
            69,
            243,
            16,
            142,
            114,
            25,
            14,
            251,
            208,
            74,
            79,
            181,
            152,
            45,
            245,
            63,
            242,
            244,
            22,
            65,
            51,
            84,
            111,
            26,
            244,
            246,
            67,
            139,
            186,
            246,
            113,
            138,
            147,
            240,
            156,
            61,
            216,
            81,
            216,
            56,
            43,
            244,
            211,
            130,
            44,
            85,
            138,
            202,
            203,
            161,
            87,
            55,
            228,
            34,
            48,
            24,
            244,
            163,
            204,
            122,
            60,
            85,
            251,
            105,
            182,
            15,
            12,
            218,
            11,
            22,
            74,
            116,
            247,
            131,
            206,
            27,
            159,
            88,
            52,
            136,
            43,
            102,
            76,
            167,
            66,
            134,
            113,
            237,
            252,
            249,
            244,
            48,
            203,
            52,
            117,
            62,
            106,
            132,
            23,
            143,
            172,
            121,
            18,
            203,
            110,
            191,
            13,
            151,
            79,
            157,
            136,
            120,
            75,
            59,
            166,
            95,
            49,
            7,
            111,
            109,
            218,
            132,
            128,
            234,
            97,
            217,
            116,
            46,
            207,
            171,
            49,
            196,
            200,
            113,
            15,
            87,
            97,
            3,
            62,
            206,
            28,
            110,
            219,
            104,
            166,
            61,
            224,
            252,
            224,
            77,
            17,
            97,
            238,
            13,
            75,
            188,
            134,
            66,
            81,
            76,
            157,
            50,
            9,
            219,
            182,
            109,
            195,
            117,
            215,
            205,
            71,
            50,
            165,
            137,
            224,
            188,
            113,
            241,
            107,
            111,
            203,
            206,
            159,
            225,
            168,
            207,
            12,
            170,
            78,
            139,
            190,
            125,
            133,
            36,
            156,
            205,
            39,
            33,
            13,
            82,
            229,
            53,
            43,
            101,
            106,
            68,
            162,
            234,
            90,
            180,
            104,
            145,
            41,
            123,
            223,
            125,
            247,
            153,
            244,
            94,
            175,
            240,
            108,
            96,
            154,
            118,
            132,
            167,
            139,
            30,
            111,
            185,
            229,
            22,
            243,
            130,
            248,
            15,
            247,
            255,
            209,
            137,
            239,
            93,
            252,
            156,
            124,
            210,
            74,
            253,
            81,
            27,
            123,
            239,
            167,
            38,
            114,
            99,
            134,
            189,
            159,
            236,
            195,
            87,
            134,
            15,
            67,
            142,
            107,
            143,
            159,
            166,
            181,
            72,
            247,
            93,
            125,
            207,
            28,
            58,
            140,
            54,
            142,
            53,
            203,
            177,
            118,
            39,
            211,
            24,
            28,
            119,
            190,
            52,
            116,
            101,
            104,
            34,
            185,
            209,
            14,
            86,
            82,
            240,
            208,
            193,
            241,
            114,
            111,
            151,
            77,
            82,
            235,
            3,
            113,
            238,
            5,
            203,
            72,
            68,
            41,
            43,
            95,
            25,
            153,
            114,
            158,
            158,
            101,
            6,
            137,
            8,
            101,
            193,
            73,
            182,
            230,
            241,
            231,
            240,
            226,
            250,
            55,
            176,
            236,
            142,
            187,
            232,
            149,
            134,
            181,
            205,
            67,
            129,
            147,
            32,
            70,
            239,
            181,
            223,
            105,
            158,
            32,
            194,
            36,
            80,
            105,
            156,
            136,
            19,
            137,
            86,
            187,
            236,
            132,
            208,
            179,
            210,
            206,
            10,
            226,
            91,
            234,
            196,
            97,
            151,
            88,
            86,
            175,
            157,
            204,
            91,
            156,
            128,
            62,
            237,
            232,
            107,
            1,
            55,
            211,
            36,
            200,
            9,
            186,
            87,
            91,
            12,
            186,
            86,
            77,
            110,
            65,
            175,
            233,
            216,
            246,
            176,
            225,
            231,
            82,
            200,
            210,
            142,
            0,
            124,
            145,
            176,
            89,
            23,
            225,
            15,
            145,
            56,
            58,
            35,
            208,
            251,
            75,
            142,
            35,
            20,
            97,
            222,
            10,
            242,
            153,
            44,
            107,
            161,
            153,
            52,
            106,
            239,
            135,
            55,
            24,
            97,
            92,
            1,
            225,
            68,
            156,
            253,
            40,
            208,
            137,
            241,
            114,
            253,
            203,
            114,
            93,
            205,
            115,
            158,
            84,
            208,
            28,
            137,
            179,
            29,
            224,
            227,
            157,
            29,
            88,
            113,
            215,
            221,
            184,
            245,
            23,
            63,
            231,
            90,
            72,
            23,
            150,
            197,
            203,
            172,
            183,
            72,
            21,
            45,
            146,
            100,
            167,
            71,
            253,
            8,
            246,
            43,
            130,
            213,
            94,
            251,
            149,
            65,
            247,
            150,
            76,
            155,
            46,
            232,
            94,
            113,
            34,
            179,
            168,
            5,
            230,
            52,
            16,
            119,
            218,
            6,
            40,
            191,
            132,
            33,
            147,
            168,
            186,
            52,
            41,
            236,
            123,
            212,
            19,
            81,
            37,
            145,
            33,
            16,
            10,
            225,
            200,
            145,
            35,
            92,
            3,
            217,
            30,
            77,
            31,
            11,
            115,
            219,
            64,
            143,
            178,
            39,
            77,
            173,
            100,
            22,
            146,
            155,
            233,
            234,
            50,
            147,
            47,
            232,
            87,
            189,
            28,
            19,
            23,
            198,
            16,
            215,
            58,
            118,
            147,
            142,
            108,
            136,
            59,
            143,
            0,
            130,
            177,
            4,
            53,
            75,
            159,
            149,
            52,
            94,
            154,
            237,
            8,
            77,
            101,
            169,
            0,
            189,
            185,
            211,
            114,
            177,
            240,
            166,
            159,
            209,
            60,
            207,
            193,
            242,
            223,
            45,
            199,
            121,
            35,
            134,
            35,
            70,
            167,
            38,
            153,
            210,
            103,
            169,
            18,
            226,
            36,
            178,
            80,
            234,
            135,
            228,
            73,
            144,
            246,
            75,
            181,
            53,
            179,
            210,
            68,
            145,
            42,
            146,
            20,
            20,
            111,
            131,
            21,
            188,
            136,
            213,
            122,
            105,
            243,
            156,
            44,
            40,
            191,
            8,
            12,
            134,
            67,
            230,
            89,
            130,
            178,
            239,
            70,
            213,
            198,
            137,
            56,
            74,
            156,
            209,
            62,
            230,
            107,
            107,
            111,
            167,
            151,
            232,
            115,
            190,
            128,
            83,
            83,
            60,
            44,
            23,
            35,
            169,
            101,
            173,
            165,
            236,
            67,
            164,
            185,
            25,
            45,
            20,
            48,
            183,
            111,
            230,
            11,
            129,
            130,
            143,
            70,
            58,
            192,
            226,
            221,
            220,
            179,
            117,
            118,
            102,
            72,
            20,
            199,
            153,
            163,
            39,
            227,
            41,
            48,
            238,
            16,
            235,
            47,
            82,
            83,
            245,
            73,
            42,
            64,
            13,
            13,
            98,
            213,
            170,
            63,
            97,
            39,
            55,
            248,
            215,
            204,
            157,
            139,
            144,
            95,
            103,
            122,
            146,
            212,
            190,
            0,
            162,
            17,
            31,
            62,
            253,
            236,
            16,
            29,
            167,
            80,
            255,
            35,
            79,
            48,
            90,
            65,
            72,
            160,
            18,
            176,
            102,
            177,
            190,
            56,
            235,
            155,
            151,
            142,
            30,
            232,
            91,
            151,
            180,
            76,
            105,
            214,
            5,
            183,
            166,
            181,
            150,
            216,
            207,
            11,
            90,
            194,
            4,
            93,
            247,
            31,
            60,
            96,
            238,
            237,
            183,
            56,
            189,
            12,
            63,
            21,
            180,
            239,
            203,
            113,
            189,
            145,
            217,
            60,
            184,
            127,
            63,
            133,
            199,
            137,
            67,
            211,
            232,
            163,
            199,
            24,
            165,
            118,
            149,
            104,
            250,
            242,
            92,
            148,
            82,
            153,
            60,
            183,
            3,
            25,
            19,
            52,
            33,
            154,
            154,
            91,
            233,
            96,
            120,
            144,
            78,
            230,
            208,
            196,
            197,
            172,
            105,
            80,
            2,
            94,
            153,
            105,
            106,
            99,
            161,
            144,
            70,
            115,
            11,
            23,
            56,
            165,
            211,
            211,
            44,
            164,
            115,
            200,
            103,
            11,
            200,
            166,
            53,
            209,
            212,
            40,
            13,
            46,
            53,
            178,
            37,
            17,
            69,
            87,
            207,
            17,
            228,
            57,
            110,
            125,
            78,
            210,
            91,
            162,
            1,
            117,
            0,
            73,
            26,
            151,
            102,
            186,
            214,
            57,
            125,
            31,
            83,
            153,
            20,
            73,
            211,
            1,
            164,
            57,
            179,
            156,
            3,
            72,
            198,
            20,
            30,
            3,
            59,
            191,
            217,
            119,
            58,
            46,
            50,
            109,
            65,
            185,
            135,
            69,
            238,
            251,
            232,
            129,
            102,
            203,
            94,
            100,
            210,
            73,
            68,
            57,
            29,
            66,
            44,
            159,
            226,
            188,
            147,
            38,
            135,
            245,
            231,
            33,
            89,
            180,
            66,
            207,
            177,
            160,
            215,
            52,
            220,
            148,
            151,
            75,
            90,
            249,
            66,
            36,
            152,
            121,
            188,
            52,
            127,
            81,
            157,
            18,
            56,
            76,
            178,
            184,
            139,
            247,
            133,
            169,
            89,
            109,
            180,
            233,
            156,
            4,
            217,
            10,
            39,
            132,
            143,
            26,
            89,
            34,
            241,
            62,
            20,
            105,
            34,
            63,
            61,
            124,
            0,
            131,
            135,
            12,
            97,
            121,
            31,
            146,
            236,
            115,
            115,
            37,
            212,
            255,
            200,
            83,
            186,
            6,
            111,
            63,
            72,
            90,
            83,
            40,
            82,
            190,
            232,
            209,
            63,
            145,
            87,
            100,
            25,
            153,
            59,
            213,
            31,
            166,
            57,
            182,
            71,
            255,
            124,
            230,
            45,
            10,
            39,
            193,
            9,
            221,
            59,
            90,
            159,
            202,
            59,
            94,
            40,
            157,
            15,
            154,
            178,
            164,
            124,
            247,
            96,
            140,
            123,
            53,
            58,
            60,
            20,
            112,
            145,
            147,
            172,
            24,
            140,
            59,
            99,
            200,
            39,
            73,
            16,
            29,
            35,
            127,
            144,
            142,
            77,
            137,
            166,
            80,
            95,
            224,
            99,
            230,
            117,
            155,
            222,
            83,
            202,
            105,
            205,
            101,
            187,
            208,
            20,
            215,
            36,
            149,
            165,
            9,
            160,
            39,
            153,
            129,
            191,
            68,
            115,
            28,
            167,
            149,
            73,
            85,
            56,
            126,
            15,
            175,
            89,
            78,
            139,
            28,
            226,
            212,
            188,
            100,
            46,
            137,
            12,
            235,
            106,
            139,
            15,
            130,
            143,
            123,
            203,
            126,
            71,
            94,
            95,
            195,
            33,
            192,
            193,
            137,
            68,
            157,
            57,
            56,
            66,
            10,
            85,
            102,
            216,
            25,
            163,
            215,
            252,
            33,
            86,
            209,
            234,
            88,
            12,
            251,
            108,
            242,
            176,
            205,
            222,
            182,
            232,
            109,
            218,
            73,
            160,
            58,
            224,
            81,
            62,
            37,
            50,
            146,
            38,
            210,
            122,
            184,
            182,
            94,
            103,
            155,
            226,
            132,
            163,
            125,
            247,
            194,
            207,
            168,
            163,
            211,
            106,
            128,
            224,
            232,
            86,
            160,
            26,
            241,
            95,
            194,
            10,
            87,
            4,
            212,
            18,
            121,
            252,
            179,
            201,
            83,
            219,
            22,
            201,
            162,
            127,
            106,
            242,
            24,
            144,
            76,
            243,
            215,
            120,
            117,
            85,
            25,
            113,
            40,
            194,
            68,
            170,
            33,
            182,
            154,
            79,
            117,
            87,
            201,
            85,
            125,
            250,
            190,
            59,
            224,
            200,
            251,
            127,
            130,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            250,
            140,
            60,
            125,
            187,
            211,
            55,
            61,
            65,
            231,
            68,
            244,
            172,
            47,
            228,
            46,
            234,
            135,
            186,
            147,
            103,
            9,
            19,
            236,
            87,
            110,
            251,
            147,
            92,
            29,
            36,
            114,
            81,
            63,
            212,
            157,
            60,
            29,
            97,
            176,
            176,
            95,
            205,
            117,
            14,
            69,
            135,
            134,
            236,
            95,
            59,
            112,
            81,
            31,
            212,
            253,
            24,
            68,
            45,
            172,
            22,
            234,
            24,
            68,
            237,
            31,
            197,
            113,
            81,
            31,
            244,
            201,
            25,
            22,
            161,
            246,
            96,
            144,
            52,
            78,
            166,
            211,
            69,
            125,
            209,
            39,
            228,
            73,
            227,
            106,
            205,
            167,
            139,
            190,
            65,
            159,
            152,
            205,
            218,
            147,
            99,
            22,
            197,
            162,
            126,
            88,
            239,
            252,
            193,
            26,
            23,
            245,
            65,
            159,
            145,
            39,
            179,
            89,
            123,
            4,
            208,
            146,
            231,
            162,
            94,
            0,
            254,
            3,
            72,
            157,
            255,
            99,
            145,
            151,
            4,
            124,
            0,
            0,
            0,
            0,
            73,
            69,
            78,
            68,
            174,
            66,
            96,
            130,
        ]
    )


from urllib.parse import urlparse


class ProxyForwarder:
    server: asyncio.Server = None
    host: str = None
    port: int = None
    scheme: str = None
    fw_host: str = None
    fw_port: int = None
    fw_scheme: str = None
    use_ssl: bool = None
    ssl_context: SSLContext = None

    @property
    def proxy_server(self):
        return self._proxy_server

    def __init__(self, proxy_server, ssl_context=None):
        self._proxy_server = None
        self.ssl_context = ssl_context

        url = urlparse(proxy_server)
        if not url.scheme:
            # check if ip:port is passed, in which case no forwarder is needed
            if url.path.find(":") != -1:
                self._proxy_server = url.path
        else:
            self.use_ssl = url.scheme == "https"

            if not url.username and not url.password:
                # if no username and password are provided in the proxy url,
                # we are not needed either
                self.scheme = url.scheme
                self._proxy_server = url.geturl()
            else:
                self.port = free_port()
                self.host = "127.0.0.1"
                self.scheme = url.scheme
                self.fw_port = url.port
                self.fw_host = url.hostname
                self.fw_scheme = url.scheme
                self.username = url.username
                self.password = url.password

                # For HTTP/HTTPS proxies, always use http:// for local forwarder
                # (local forwarder accepts plain HTTP CONNECT and handles SSL to upstream)
                if self.scheme.startswith("http"):
                    self._proxy_server = f"http://{self.host}:{self.port}"
                else:
                    self._proxy_server = f"{self.scheme}://{self.host}:{self.port}"

                logger.info(
                    "%s proxy with authentication is requested : %s"
                    % (self.scheme, proxy_server)
                )
                logger.info("starting forward proxy on %s:%d" % (self.host, self.port))
                logger.info("which forwards to %s" % proxy_server)
                asyncio.ensure_future(self.listen())

    async def listen(self):
        self.server = await asyncio.start_server(
            self.handle_request, host=self.host, port=self.port
        )
        await self.server.start_serving()

    async def handle_request(
        self, reader: asyncio.StreamReader, writer: asyncio.StreamWriter
    ):
        if self.scheme.startswith("socks"):
            return await self.handle_socks_request(reader, writer)
        elif self.scheme.startswith("http"):
            return await self.handle_http_request(reader, writer)

    async def handle_http_request(
        self, reader: asyncio.StreamReader, writer: asyncio.StreamWriter
    ):
        """
        Handle HTTP CONNECT proxy requests with authentication.
        This implements an HTTP proxy that accepts unauthenticated connections
        and forwards them to an authenticated upstream HTTP proxy.
        """
        import base64
        import ssl

        MAX_LINE_LENGTH = 8192
        REQUEST_TIMEOUT = 5.0
        UPSTREAM_CONNECT_TIMEOUT = 30.0

        remote_writer = None
        pipe_tasks = []

        try:
            try:
                request_line = await asyncio.wait_for(
                    reader.readline(), timeout=REQUEST_TIMEOUT
                )
            except asyncio.TimeoutError:
                logger.warning("Client request timeout")
                writer.write(b"HTTP/1.1 408 Request Timeout\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            if not request_line:
                writer.close()
                await writer.wait_closed()
                return

            if len(request_line) > MAX_LINE_LENGTH:
                logger.warning(f"Oversized request line: {len(request_line)} bytes")
                writer.write(b"HTTP/1.1 431 Request Header Fields Too Large\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            request_line = request_line.decode("utf-8", errors="ignore")

            if not request_line.startswith("CONNECT"):
                logger.warning(f"Non-CONNECT request received: {request_line.strip()}")
                writer.write(b"HTTP/1.1 400 Bad Request\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            parts = request_line.split()
            if len(parts) < 2:
                logger.warning(f"Malformed CONNECT request: {request_line.strip()}")
                writer.write(b"HTTP/1.1 400 Bad Request\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            target_host_port = parts[1]

            if ":" not in target_host_port:
                logger.warning(
                    f"Invalid target format (missing port): {target_host_port}"
                )
                writer.write(b"HTTP/1.1 400 Bad Request\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            try:
                host, port_str = target_host_port.rsplit(":", 1)
                port = int(port_str)
                if port < 1 or port > 65535:
                    raise ValueError("Port out of range")
            except ValueError:
                logger.warning(f"Invalid port in target: {target_host_port}")
                writer.write(b"HTTP/1.1 400 Bad Request\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            try:
                while True:
                    header = await asyncio.wait_for(
                        reader.readline(), timeout=REQUEST_TIMEOUT
                    )
                    if len(header) > MAX_LINE_LENGTH:
                        logger.warning("Oversized header line")
                        writer.write(
                            b"HTTP/1.1 431 Request Header Fields Too Large\r\n\r\n"
                        )
                        await writer.drain()
                        writer.close()
                        await writer.wait_closed()
                        return
                    if not header or header == b"\r\n" or header == b"\n":
                        break
            except asyncio.TimeoutError:
                logger.warning("Timeout reading client headers")
                writer.write(b"HTTP/1.1 408 Request Timeout\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            try:
                conn_params = {"host": self.fw_host, "port": self.fw_port}

                if self.use_ssl:
                    if self.ssl_context:
                        conn_params["ssl"] = self.ssl_context
                    else:
                        conn_params["ssl"] = ssl.create_default_context()

                remote_reader, remote_writer = await asyncio.wait_for(
                    asyncio.open_connection(**conn_params),
                    timeout=UPSTREAM_CONNECT_TIMEOUT,
                )
            except asyncio.TimeoutError:
                logger.error(
                    f"Timeout connecting to upstream proxy {self.fw_host}:{self.fw_port}"
                )
                writer.write(b"HTTP/1.1 504 Gateway Timeout\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return
            except Exception as e:
                logger.error(f"Failed to connect to upstream proxy: {e}")
                writer.write(b"HTTP/1.1 502 Bad Gateway\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                return

            credentials = f"{self.username}:{self.password}"
            auth_encoded = base64.b64encode(credentials.encode()).decode("ascii")

            connect_request = (
                f"CONNECT {target_host_port} HTTP/1.1\r\n"
                f"Host: {target_host_port}\r\n"
                f"Proxy-Authorization: Basic {auth_encoded}\r\n"
                f"Proxy-Connection: Keep-Alive\r\n"
                f"\r\n"
            )

            remote_writer.write(connect_request.encode())
            await remote_writer.drain()

            try:
                response_line = await asyncio.wait_for(
                    remote_reader.readline(), timeout=REQUEST_TIMEOUT
                )
            except asyncio.TimeoutError:
                logger.error("Timeout reading upstream proxy response")
                writer.write(b"HTTP/1.1 504 Gateway Timeout\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                remote_writer.close()
                await remote_writer.wait_closed()
                return

            if not response_line:
                logger.error("No response from upstream proxy")
                writer.write(b"HTTP/1.1 502 Bad Gateway\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                remote_writer.close()
                await remote_writer.wait_closed()
                return

            response_line_str = response_line.decode("utf-8", errors="ignore")

            upstream_headers = []
            try:
                while True:
                    header = await asyncio.wait_for(
                        remote_reader.readline(), timeout=REQUEST_TIMEOUT
                    )
                    if not header or header == b"\r\n" or header == b"\n":
                        break
                    upstream_headers.append(header)
            except asyncio.TimeoutError:
                logger.error("Timeout reading upstream proxy headers")
                writer.write(b"HTTP/1.1 504 Gateway Timeout\r\n\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                remote_writer.close()
                await remote_writer.wait_closed()
                return

            if "200" in response_line_str:
                writer.write(b"HTTP/1.1 200 Connection Established\r\n\r\n")
                await writer.drain()

                event = asyncio.Event()
                pipe_tasks = [
                    asyncio.create_task(self.pipe(remote_reader, writer, event)),
                    asyncio.create_task(self.pipe(reader, remote_writer, event)),
                ]

                try:
                    await asyncio.gather(*pipe_tasks)
                finally:
                    # Ensure tasks are cancelled and cleaned up to prevent resource leaks
                    for task in pipe_tasks:
                        if not task.done():
                            task.cancel()
                    await asyncio.gather(*pipe_tasks, return_exceptions=True)
            else:
                logger.error(
                    f"Upstream proxy rejected connection: {response_line_str.strip()}"
                )
                writer.write(b"HTTP/1.1 502 Bad Gateway\r\n")
                writer.write(b"Content-Type: text/plain\r\n")
                writer.write(b"\r\n")
                writer.write(b"Upstream proxy rejected the connection\r\n")
                await writer.drain()
                writer.close()
                await writer.wait_closed()
                remote_writer.close()
                await remote_writer.wait_closed()

        except Exception as e:
            logger.error(f"Error handling HTTP proxy request: {e}", exc_info=True)
            try:
                writer.write(b"HTTP/1.1 500 Internal Server Error\r\n\r\n")
                await writer.drain()
            except:
                pass
        finally:
            try:
                if not writer.is_closing():
                    writer.close()
                    await writer.wait_closed()
            except:
                pass

            try:
                if remote_writer and not remote_writer.is_closing():
                    remote_writer.close()
                    await remote_writer.wait_closed()
            except:
                pass

            for task in pipe_tasks:
                if not task.done():
                    task.cancel()

    async def handle_socks_request(
        self, reader: asyncio.StreamReader, writer: asyncio.StreamWriter
    ):
        import socket
        from struct import calcsize, error, pack, unpack

        NO_ADDR = "0.0.0.0"
        ATYP_IPv4 = 0x01
        ATYP_DNS = 0x03
        ATYP_IPv6 = 0x04

        # import aiosocks2
        async def read(fmt):
            """
            Read from the byte stream
            :param str fmt: struct format specifier
            :return tuple:
            """
            data = await reader.read(calcsize(fmt))
            try:
                return unpack(fmt, data)
            except error as e:
                if "buffer" in str(e):
                    logger.debug(
                        f"socks proxy read invalid data {e.args[0]}  - got {data} ({len(data)} bytes)"
                    )
                raise

        try:
            version, num_methods = await read("!BB")
        except error as e:
            return

        # fire and forget socks auth methods
        await read("!" + "B" * num_methods)

        # we only need to auth with the upstream proxy
        writer.write(pack("!BB", version, 0))

        # read command from the client
        version, cmd, resv, atyp = await read("!BBBB")

        if atyp == ATYP_IPv4:
            ip_packed = await reader.read(4)
            port = (await read("!H"))[0]
            ip_addr = socket.inet_ntop(socket.AF_INET, ip_packed)
            hostname = None
        elif atyp == ATYP_IPv6:
            ip_packed = await reader.read(16)
            port = (await read("!H"))[0]
            ip_addr = socket.inet_ntop(socket.AF_INET6, ip_packed)
            hostname = None
        elif atyp == ATYP_DNS:
            hostname_len = (await read("!B"))[0]
            hostname = (await read("!{}s".format(hostname_len)))[0]
            port = (await read("!H"))[0]
            ip_addr = None

        if hostname:  # noqa
            if not ip_addr:  # noqa
                ip_addr = socket.gethostbyname(hostname)  # noqa
        else:
            hostname = socket.gethostbyaddr(ip_addr)  # noqa

        # connect to the upstream proxy
        remote_reader, remote_writer = await asyncio.open_connection(
            host=self.fw_host, port=self.fw_port
        )

        # handshake with upstream proxy
        remote_writer.write(pack("!BBB", version, 1, 2))
        server_version, server_auth_method = await remote_reader.read(calcsize("!BB"))

        #  authenticate to upstream proxy
        if server_auth_method == 2:
            auth_ticket = pack(
                f"!BB{len(self.username)}sB{len(self.password)}s",
                1,
                len(self.username),
                self.username.encode(),
                len(self.password),
                self.password.encode(),
            )

            remote_writer.write(auth_ticket)
            await remote_writer.drain()
            ver, result = await remote_reader.read(calcsize("!BB"))

            if result != 0:
                raise Exception("socks authentication error: %s" % result)

        # forward client socks5 message to upstream proxy
        remote_writer.write(pack("!BBBB", version, cmd, resv, atyp))
        remote_writer.write(pack("!B", hostname_len))
        remote_writer.write(pack(f"!{hostname_len}s", hostname))
        remote_writer.write(pack("!H", port))

        # create a tunnel between client and upstream proxy
        event = asyncio.Event()
        tasks = self.pipe(remote_reader, writer, event), self.pipe(
            reader, remote_writer, event
        )
        await asyncio.gather(*tasks)

    @staticmethod
    async def pipe(
        reader: asyncio.StreamReader, writer: asyncio.StreamWriter, event: asyncio.Event
    ):
        logger.debug("client proxy to authenticated proxy pipe")
        while not event.is_set():
            try:
                data = await asyncio.wait_for(reader.read(2**16), 1)
                if not data:
                    break
                # simply forward

                writer.write(data)
            except asyncio.TimeoutError:
                continue
        event.set()
